
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>

typedef int ElemType;
typedef struct {
    ElemType len;
    ElemType *str;
} SSTable;

void SST_Init(SSTable &T, SSTable &T1, SSTable &T2, ElemType len) {
    T.len = T1.len = T2.len = len;
    T.str = (ElemType *) malloc(sizeof(ElemType) * T.len);
    T1.str = (ElemType *) malloc(sizeof(ElemType) * T1.len);
    T2.str = (ElemType *) malloc(sizeof(ElemType) * T2.len);

    for (int i = 0; i < T.len; i++) {
        int num;
        scanf("%d", &num);
        T2.str[i] = T1.str[i] = T.str[i] = num;
    }
}

int compare(const void *left, const void *right) {
    return *(int *) (left) - *(int *) (right);
}

void SST_print(SSTable T) {
    for (int i = 0; i < T.len; i++) {
        printf("%3d", T.str[i]);
    }
    printf("\n");
}

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

void BubbleSort(ElemType *str, int len) {
    bool flag;
    for (int i = 0; i < len - 1; i++) {
        for (int j = len - 1; j > i; j--) {
            flag = false;
            if (str[j - 1] > str[j]) {
                swap(str[j - 1], str[j]);
                flag = true;
            }
        }
    }
    if (!flag) {
        return;
    }
}

int partition(ElemType *str, int low, int high) {
    int pivot = str[low];//拿到最小的值作为分割值

    while (low < high) {
        //从后往前遍历，找到比分割值小的数
        while (low < high && str[high] >= pivot) high--;
        str[low] = str[high];
        while (low < high && str[low] <= pivot) low++;
        str[high] = str[low];
    }
    str[low] = pivot;
    return low;
}

void QuickSort(ElemType *str, int low, int high) {
    if (low < high) {
        int pivot = partition(str, low, high);
        QuickSort(str, low, pivot - 1);
        QuickSort(str, pivot + 1, high);
    }
}

void InsertSort(ElemType *str, ElemType len) {
    int insertVal, i, j;
    for (i = 1; i < len; i++) {
        insertVal = str[i];
        for (j = i - 1; j >= 0 && str[j] > insertVal; j--) {
            str[j + 1] = str[j];
        }
        str[j + 1] = insertVal;
    }
}

int main() {
    SSTable t, t1, t2;
    SST_Init(t, t1, t2, 10);
    //冒泡排序
    BubbleSort(t.str, t.len);
    SST_print(t);
    //快排
    QuickSort(t1.str, 0, t1.len - 1);
    SST_print(t1);
    //插入排序
    InsertSort(t2.str, t2.len);
    SST_print(t2);

    return 0;
}
